/**
 * 快速排序：
 * ⑴ 选择一个基数点，arr[0]，左右两个哨兵i, j，右边哨兵先开始移动j--，直到找到第一个小于基数的位置，
 * ⑵ 开始移动左边哨兵i++，直到找到第一个大于基数的位置，保存下来
 * ⑶ 交换i和j的位置，重复1和2，直到i和j相遇，退出循环
 * ⑷ 相遇的位置的数字和基数比较，如果较小，则交换arr[0]和arr[i]位置，此时数组状态是基数左侧都小于基数，基数右侧都大于基数
 * ⑸ 使用slice方法切割左右两侧数组，递归重复1 2 3 4步骤，把每次递归的结果都拼接起来，即可得到最终排序后结果
 * 递归退出的条件是左右两侧的数字都小于等于1，就不需要再次进行递归了
 * 特点：跳跃式交换，比较次数减少
 * @param {Array} nums 
 * @returns Array
 */
var quickSort = function (nums) {
  let index = 0;

  function qsort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
    let base = arr[0];
    let i = 1;
    let j = arr.length - 1;
    let result = [];
    while (i < j) {
      let A = arr[i];
      let B = arr[j];
      if (B > base) {
        j--;
        continue;
      }
      if (A < base) {
        i++;
        continue;
      }
      console.log('走不到这里来', j, i)
      // 交换两个哨兵的位置
      arr[i] = B;
      arr[j] = A;
      // 哨兵继续移动
      j--;
    }
    // 当两个哨兵相遇，且当前位置比哨兵小，则交换相遇位置与基数
    if (arr[i] < base) {
      arr[0] = arr[i];
      arr[j] = base;
    }
    console.log(i, j)
    // 此时 基准左边均小于基准，基准右边均大于基准
    // 分置处理
    let left = arr.slice(0, i);
    let right = arr.slice(i + 1, arr.length);
    console.log('original：', index++, arr, left, right);
    if (left.length <= 1 && right.length <= 1) {
      return arr;
    }
    let leftSort = qsort(left);
    let rightSort = qsort(right);
    console.log('dp：', index++, leftSort, rightSort)
    return result.concat(leftSort).concat(base).concat(rightSort);
  }
  nums = qsort(nums);
  return nums;
}

var quickSort2 = function(nums) {
  if (nums.length <= 1) {
    return nums; //如果数组只有一个数，就直接返回；
  }
  // 取中间数据
  let num = Math.floor(nums.length / 2);
  // 找出中间这个数，并且从数组中删除
  let target = nums.splice(num, 1)
  let left = [];
  let right = [];
  for (let i = 0; i < nums.length; i++) {
    const element = nums[i];
    if(element < target) {
      left.push(element)
    } else {
      right.push(element);
    }
  }
  return quickSort2(left).concat([target], quickSort2(right));
}

// console.log(quickSort([5,8,4,3,1,0,7]))

var digital = []; 
var str = []; 
"1233fddfd&3434fdsaff&454545&4545444rfdsfds&545gdsgs".replace(/[^a-z0-9]/g, '')
.replace(/([a-z])|(\d)/g, function(a,b,c) {
  if(digital.indexOf(a) === -1 && !isNaN(a)) {
    digital.push(a)
  }
  else if(isNaN(a) && str.indexOf(a) === -1) {
    str.push(a)
  }
  return '-'
})
console.log(str.sort(), digital.sort())